The present invention relates generally to error correction in macro bar code symbols.
This invention further relates generally to the optical scanning of two dimensional bar code symbols and in particular to the optical scanning of a randomly oriented two-dimensional bar code symbol by first determining the orientation of the symbol with respect to the field of view of the scanning device and then rotating the field of view accordingly so as to be aligned substantially with the symbol for scanning and further processing and decoding as known from U.S. Pat. No. 5,523,552 incorporated herein by reference.
xe2x80x9cMacroxe2x80x9d bar code symbols allow large documents to be encoded into multiple symbols, preferably two-dimensional symbols. If one of those symbols is lost it may not be possible to recreate the document; this cannot be remedied by adding more error correction code words into the individual symbols.
The invention further addresses problems with known error correction systems, in particular where data is encoded across a plurality of symbols using a xe2x80x9cmacroxe2x80x9d code. In known systems, there can be a very high time penalty where individual symbols are lost.
The invention further relates to decoding bar code symbols in which the error correction capability allows the user to prioritise the importance of the codewords within a symbol.
The use of encoded data placed on certain types of records is advantageous in that a large amount of information can be placed in a relatively small area.
Also, encoded information can be kept confidential and revealed only to person having the appropriate decoding apparatus.
Known records that could best utilize the benefits of having encoded data placed thereon are records where the data does not change over the life of the record; or where there are relatively large time gaps before the record or such encoded data become outdated. In such systems such records, which include price tags, package identifiers, or train car identifiers for example, do not require frequent updating of the data. Another alternative was to make the record large enough to accommodate additional encoded data representations for supplementing the information from time to time.
There are several types of records where the benefits of having encoded data thereon were offset by the necessity of frequent updating of the encoded information. For example, health cards and records could beneficially include encoded data because they required large amounts of necessary information and the need for confidentiality. Charge cards, where the remaining available credit could be printed on the card as each purchase is made, could beneficially include encoded data. Admission tickets useful for multiple events could include the used or unused events as encoded data on the ticket. This would include tickets for seminars with several workshops, or an admission ticket to an amusement park that includes several rides and shows. In all of the above instances, the necessity of frequent updating of the encoded information would either result in an oversized cumbersome record, or the frequent replacement of the record with a new record having updated encoded data.
One proposed solution to this is a record which contains a printed portion placed on the record and an information portion including removable information encoded in an error-correctable, machine-readable format.
A printer system for a record containing text in at least a portion thereof, comprises input means for receiving information to be placed onto the record; encoding means, coupled to the input means, for encoding the received information in an error-correctable, machine-readable format; and output means, coupled to the coding means, including means for removing any encoded information other than the received information from a record, and means for removably placing the encoded information on the record.
A reader system for a record having an information area containing removable information encoded in an error-correctable format and text, comprises reading means for extracting the information from the information area; correction means, coupled to the reading means, for performing error correction on the removable information to correct any errors in the extracted information and output.
According to another aspect, bar codes have become broadly accepted as a means for automatically identifying objects. A bar code symbol is a pattern of parallel bars and spaces of various widths that represent data elements or characters. The bars represent strings of binary ones and the spaces represent strings of binary zeros. Generally, the bars and spaces can be no smaller than a specified minimum width which is called a xe2x80x9cmodulexe2x80x9d or xe2x80x9cunitxe2x80x9d. The bars and spaces are multiples of this module size or minimum width.
The conventional bar code symbol is xe2x80x9cone-dimensionalxe2x80x9d in that the bars and spaces extend only in a single direction. There has been an increasing need, however, for machine-readable symbols that contain more information than conventional bar code symbols. One approach for increasing the information in machine-readable symbols is to reduce the height of the bar codes and stack the bar codes one on top of each other to create a xe2x80x9cstackedxe2x80x9d or xe2x80x9ctwo-dimensionalxe2x80x9d bar code. One such two-dimensional bar code is PDF417, which was developed by Symbol Technologies, Inc. The PDF417 symbology utilizes a variable number of codewords which are discrete representations of data. A complete description of the PDF417 code is contained in U.S. Pat. No. 5,304,786, which is assigned to the same assignee as the present invention and which is incorporated by reference herein. Other two dimensional bar code symbologies include Code 1 and Maxicode, which are referred to as matrix codes.
Both one-dimensional and two-dimensional bar code symbols are typically read by optical scanning techniques, such as scanning laser beams, and the resulting electrical signals are then decoded to recover the date encoded in the symbol. In particular, two-dimensional bar codes symbols such as those in the PDF417 symbology are advantageously scanned by a two-dimensional mastering laser pattern, which is comprised of a series of horizontal scans repeatedly swept in a vertical direction, as described in U.S. Pat. Nos. 4,816,661 and 5,235,167, which patents are assigned to the assignee of the present application and are incorporated by reference herein. When scanning and decoding a two-dimensional bar code symbol, however, the horizontal scan lines of the laser raster must be aligned substantially with the horizontal rows of the symbol, usually within xc2x13xc2x0. The laser scan lines form a field of view and are parallel with the horizontally located rows of a PDF417 symbol, which will allow successful decoding.
However, the symbol tilted with respect to the scan lines in the field of view such that the symbol cannot be successfully decoded. Although a two-dimensional bar code such as PDF417 allows some deviation, the orientation of the field of view must still be less than some maximum angle relative to the rows of the symbol.
When using a hand-held laser rastering scanner, it is fairly simple for the operator to physically align the raster pattern in the field of view with the two-dimensional symbol by rotating the reader and/or the object bearing the symbol until the requisite alignment of the field of view is obtained visually and the symbol is successfully read and decoded. There are many applications, however, in which it is desirable to be able to read and decode a two-dimensional bar code symbol that may be randomly oriented without having to manually move the reader such that the field of view is aligned with rows of the symbol. For example, in an industrial environment, the symbol may be located on an object moving along a conveyor belt where the reader views the symbol from above. Thus, the symbol may be in any orientation relative to the field of view of the reader. In addition, in a retail point-of-sale environment, the symbol may be located on an item presented to a cashier for purchase. The cashier typically puts the item bearing the symbol under a presentation scan lamp, which provides the appropriate laser scanning pattern. It is thus desirable in this situation to allow the cashier to quickly present the item under the scan lamp without having to align the symbol with the raster pattern.
Bar code symbol reading devices are also known in the art which are based upon charge coupled device (CCD) imaging technology. For example, a two dimensional CCD array comprised of 512xc3x97512 elements may be used to capture an image for the entire target bar code symbol simultaneously, and the electric charge stored in each element as a function of the amount of light sensed by an area covered by each element is shifted out serially to form electric signals for further processing, digitizing and decoding. Image processing techniques allow such a CCD array to be used to read misoriented bar code symbols. For example, U.S. Pat. No. 5,319,181 issued to the assignee of the present invention, describes a technique to implement a CCD camera to capture a PDF417 symbol, store the image data in memory, and perform virtual scanning of the image data to determine the proper orientation of the symbol and enable successful decoding. These techniques, while satisfactory in many applications, do not allow high speed racing since the image memory must be repeatedly accessed in a random access manner. There is thus a need in the art for CCD based bar code symbol reading devices to be able to perform high speed reading of misoriented two dimensional bar code symbols.
One proposed solution set out in U.S. Pat. No. 5,523,552 identified above is to provide a method and apparatus for automatically aligning a field of view of a two-dimensional bar code symbol reading device with a randomly oriented two-dimensional bar code symbol, wherein the symbol comprises a unique locatable pattern located along at least one side thereof, the method comprising the steps of scanning the symbol with a scan line extending through the pattern, detecting the pattern, measuring the length of the pattern detected by the scan line, and rotating by a predetermined amount the scan line about a point central in the field of view. These scanning, detecting, measuring, and rotating steps are repeated for a predetermined number of times. The rotation angle at which the pattern length is smallest is determined as a function of the measured pattern lengths, and the field of view of the symbol reading device is rotated to the determined skew angle so as to be aligned with the symbol for subsequent scanning and decoding.
It is an object of the invention to overcome or mitigate problems encountered with known arrangements.
It is a particular object to provide a xe2x80x9cmacroxe2x80x9d bar code system capable of recovering the entire code even is where an individual symbol is lost.
It is a further object of the invention to provide an error correction scheme which is quicker than known schemes.
It is a further object of the invention to provide for the select-on of an appropriate security level for a symbol and to provide an adjustable security level, and to allow decoding of a portion of a symbol even when the symbol cannot be completely decoded.
Additional objects and advantages of this invention will be set forth in part of the description which follows, and in part will be obvious from that description, or may be learned by practice of this invention. The advantages of this invention may be realized and attained by means of the instrumentalities and combinations particularly pointed out in the appended claims.
The accompanying drawings, which are incorporated in and constitute a part of the specification, illustrate embodiments of the invention and, together with the general description, serve to explain the principles of the invention.